package top.datacluster.basic.algorithm.leetcode.stack;

import top.datacluster.basic.algorithm.leetcode.link.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode1019 {

    public int[] nextLargerNodes(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> index = new Stack<>();
        int i = 0;
        List<Integer> result = new ArrayList<>();
        while (head != null){
            if (stack.isEmpty()){
                stack.push(head.val);
                index.push(i);
            }else{
                while (!stack.isEmpty() && stack.peek() < head.val){
                    int temp = stack.pop();
                    int j = index.pop();
                    result.set(j, head.val);
                }
                stack.push(head.val);
                index.push(i);
            }
            i++;
            head = head.next;
            result.add(0);
        }
        int[] res = new int[result.size()];
        for (i = 0; i < result.size(); i++){
            res[i] = result.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;

        new LeetCode1019().nextLargerNodes(l1);
    }
}
